package 数据结构专栏.B_链表专栏;

/**
 * @Title
 * @Author zhengqiang.tan
 * @Date 2021/4/17 5:19 PM
 */
public class 反转单链表 {
    /**
     * 递归 https://blog.csdn.net/qq_33958946/article/details/84326965
     *
     * <p>
     * 如果当前节点或者当前节点的下一节点为空，直接返回该节点；
     * 否则使该节点的后一节点指向该节点，以此递归。
     */
    public static ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode nextNode = head.next; //得到当前节点的下一节点
        head.next = null; //打断当前指针链
        ListNode res = reverseList3(nextNode); //每次递归下一节点进行反转
        nextNode.next = head;//反转指针域
        return res;
    }

    // 迭代方式
    public static ListNode reverseList(ListNode curr) {
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }


    // v1: 递归写法，
    public static ListNode reverseListV1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = reverseListV1(head.next); // 递归调用，直到条件为null,获取最后一个节点作为头节点返回
        head.next.next = head; // 下一个节点
        head.next = null; //
        return cur;

    }
}
